package class19;

import java.util.*;

/**
 * @author YZY
 * @since 2022/8/18 22:11
 * <a href="https://leetcode.cn/problems/stickers-to-spell-word/">691. 贴纸拼词</a>
 */
public class Code03_StickersToSpellWord {

    /**
     * 暴力尝试
     */
    public static int minStickers1(String[] stickers, String target) {
        int ans = process1(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private static int process1(String[] stickers, String target) {
        if (target.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String first : stickers) {
            String rest = minus1(target, first);
            if (rest.length() != target.length()) {
                min = Math.min(min, process1(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    private static String minus1(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] count = new int[26];
        for (char cha : str1) {
            count[cha - 'a']++;
        }
        for (char cha : str2) {
            count[cha - 'a']--;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    builder.append((char) (i + 'a'));
                }
            }
        }
        return builder.toString();
    }

    /**
     * 记忆化搜索
     */
    public static int minStickers3(String[] ss, String target) {
        // 将stickers字符串数组，转成字符数组
        int[][] stickers = new int[ss.length][26];
        for (int i = 0; i < ss.length; ++i) {
            char[] chars = ss[i].toCharArray();
            for (char ch : chars) {
                stickers[i][ch - 'a']++;
            }
        }
        Map<String, Integer> dp = new HashMap<>();
        int result = process3(stickers, dp, target);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private static int process3(int[][] stickers, Map<String, Integer> dp, String tar) {
        if (dp.containsKey(tar)) {
            return dp.get(tar);
        }
        if (tar.isEmpty()) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        char[] target = tar.toCharArray();
        for (int[] sticker : stickers) {
            // 剪枝，如果说当前的贴纸没有能减去target中开头字符，就先跳过
            // 我们可以先选择能将target开头字符减去的贴纸，最后结果不会变
            if (sticker[target[0] - 'a'] == 0) {
                continue;
            }
            // 到这一步说明当前贴纸可以减去target开头的字符，开始拿贴纸，直到target开头字符拿空
            String reset = minus3(target, sticker);  // 这里封装一下减去的方法，使得代码可读性高
            // 当前贴纸拿完就可以选择下一个贴纸，并更新一下拿的最小贴纸数
            min = Math.min(min, process3(stickers, dp, reset));
        }
        dp.put(tar, min + (min == Integer.MAX_VALUE ? 0 : 1));
        // 如果不是系统最大值，那么就需要加上自身的贴纸，因为min是当前贴纸往后找的贴纸数，不包含当前贴纸自身
        return dp.get(tar);
    }

    // 减去的方法
    private static String minus3(char[] target, int[] sticker) {
        int[] tarCount = new int[26];  // 转成词频数组
        // 统计词频
        for (char ch : target) {
            tarCount[ch - 'a']++;
        }
        // 拼接减去贴纸中还剩下的词频
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < tarCount.length; ++i) {
            tarCount[i] -= sticker[i];
            if (tarCount[i] <= 0) {
                continue;
            }
            res.append(String.valueOf((char) (i + 'a')).repeat(tarCount[i]));
        }
        return res.toString();
    }

}
